package com.ztom.offer.v2;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 栈的压入、弹出序列
 * <p>
 * https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 *
 * @author ZhangTao
 */
public class Code29ValidateStackSequences {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0;
        for (int num : pushed) {
            // 模拟入栈
            stack.offerLast(num);
            // 模拟出栈
            while (!stack.isEmpty() && stack.peekLast() == popped[i]) {
                stack.pollLast();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
